package com.demo.datastructure.reorder.countingSort;

import java.util.Random;

/**
 * @description: 计数排序
 * @author: ljr
 * @time: 2021/5/6 20:38
 * @since 1.0
 */
public class MyCountingSort2 {

    public static void countingSort(int[] a, int n){
        if (n <= 1) return;
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; ++i) {
            if (max < a[i]) {
                max = a[i];
            }
        }

        int[] c = new int[max + 1];

        // 申请一个计数数组c，下标大小[0,max]
        for (int i = 0; i <= max; ++i) {
            c[i] = 0;
        }

        // 计算每个元素的个数，放入c中
        for (int i = 0; i < n; ++i) {
            c[a[i]]++;
        }

        // 依次累加
        for (int i = 1; i <= max; ++i) {
            c[i] = c[i-1] + c[i];
        }

        // 临时数组r，存储排序之后的结果
        int[] r = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            int index = c[a[i]]-1;
            r[index] = a[i];
            c[a[i]]--;
        }

        // 将结果拷贝给a数组
        for (int i = 0; i < n; ++i) {
            a[i] = r[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[10000000];
        Random random = new Random();
        for(int i = 0; i < nums.length; i++){
            nums[i] = random.nextInt(1000000)+10000;
        }

        long cu = System.currentTimeMillis();
        MyCountingSort.countingSort(nums,nums.length);
        System.out.println(System.currentTimeMillis()-cu);
    }
}
